# -*- coding: utf-8 -*-

'''

@author: wyndem
@Emil:   wyndem.wen@timevary.com
@FileName: chapter_2.py
@Time: 2018/6/22 10:42
@Description: 选择排序，时效：O(n^2)

'''



def findSmallest(arr):
    smallest=arr[0]
    smallest_index=0
    for i in range(1,len(arr)):
        if arr[i] < smallest:
            smallest=arr[i]
            smallest_index=i
    return smallest_index


def selectionSort(arr):
    newArr=[]
    for i in range(len(arr)):
        smallest=findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr


if __name__ == '__main__':
    print(selectionSort([5,9,6,4,3,4,1,0,45,85]))